<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Hard
  </div>
  <div>
   <h1 class="question_title">
    458. Poor Pigs
   </h1>
   <p>
    There are 1000 buckets, one and only one of them is poisonous, while the rest are filled with water. They all look identical. If a pig drinks the poison it will die within 15 minutes. What is the minimum amount of pigs you need to figure out which bucket is poisonous within one hour?
   </p>
   <p>
    Answer this question, and write an algorithm for the general case.
   </p>
   <p>
    &nbsp;
   </p>
   <p>
    <b>
     General case:
    </b>
   </p>
   <p>
    If there are
    <code>
     n
    </code>
    buckets and a pig drinking poison will die within
    <code>
     m
    </code>
    minutes, how many pigs (
    <code>
     x
    </code>
    ) you need to figure out the
    <strong>
     poisonous
    </strong>
    &nbsp;bucket within
    <code>
     p
    </code>
    minutes? There is exactly one bucket with poison.
   </p>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     Note:
    </strong>
   </p>
   <ol>
    <li>
     A pig can be allowed to drink simultaneously on as many buckets as one would like, and the feeding takes no time.
    </li>
    <li>
     After a pig has instantly finished drinking buckets, there has to be a
     <strong>
      cool down time
     </strong>
     of
     <em>
      m&nbsp;
     </em>
     minutes. During this time, only observation is allowed and no feedings at all.
    </li>
    <li>
     Any given bucket can be sampled an infinite number of times (by an unlimited number of pigs).
    </li>
   </ol>
  </div>
  <div>
   <h1 class="question_title">
    458. 可怜的小猪
   </h1>
   <p>
    有 1000 只水桶，其中有且只有一桶装的含有毒药，其余装的都是水。它们从外观看起来都一样。如果小猪喝了毒药，它会在 15 分钟内死去。
   </p>
   <p>
    问题来了，如果需要你在一小时内，弄清楚哪只水桶含有毒药，你最少需要多少只猪？
   </p>
   <p>
    回答这个问题，并为下列的进阶问题编写一个通用算法。
   </p>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     进阶:
    </strong>
   </p>
   <p>
    假设有
    <code>
     n
    </code>
    只水桶，猪饮水中毒后会在
    <code>
     m
    </code>
    分钟内死亡，你需要多少猪（
    <code>
     x
    </code>
    ）就能在
    <code>
     p
    </code>
    分钟内找出 &ldquo;
    <strong>
     有毒
    </strong>
    &rdquo; 水桶？这&nbsp;
    <code>
     n
    </code>
    只水桶里有且仅有一只有毒的桶。
   </p>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     提示：
    </strong>
   </p>
   <ol>
    <li>
     可以允许小猪同时饮用任意数量的桶中的水，并且该过程不需要时间。
    </li>
    <li>
     小猪喝完水后，必须有
     <em>
      m
     </em>
     分钟的
     <strong>
      冷却时间
     </strong>
     。在这段时间里，只允许观察，而不允许继续饮水。
    </li>
    <li>
     任何给定的桶都可以无限次采样（无限数量的猪）。
    </li>
   </ol>
  </div>
 </body>
</html>